package com.backpack;

public class OnesandZeroes0111_474 {
    public int findMaxForm(String[] strs, int m, int n) {

        //dp[i][j] 表示 容量为（ i个0、j个1）的子集合，最大长度为dp[i][j]
        int[][] dp = new int[m+1][n+1];

        //初始化
        dp[0][0] = 0;

        for (String str: strs) {
            int num_0 = 0;
            int num_1 = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') num_0++;
                else num_1++;
            }
            for (int i = m; i >= num_0; i--) {
                for (int j = n; j >= num_1; j--) {
                    dp[i][j] = Math.max(dp[i-num_0][j-num_1] + 1,dp[i][j]);
                }
            }
        }
        return dp[m][n];
    }
}
